package collectionsUtils;

/**
 * 功能描述:前缀和数组
 * 2025/04/19
 *
 * @author ZhangYi
 */
public class PrefixSumArray {

	public static void main(String[] args) {
		int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
		PrefixSum prefixSum = new PrefixSum(arr);
		int L = 0, R = 6;
		int range = prefixSum.range(L, R);
		System.out.println(range);

		PrefixSum2 prefixSum2 = new PrefixSum2(arr);
		int range1 = prefixSum2.range(L, R);
		System.out.println(range1);
	}

}


class PrefixSum {
	private int[] preSum;

	/**
	 * 前缀总和
	 *
	 * @param array 阵列
	 * @author ZhangYi
	 */
	public PrefixSum(int[] array) {
		int N = array.length;
		this.preSum = new int[N];
		preSum[0] = array[0];
		for (int index = 1; index < N; index++) {
			preSum[index] = array[index] + preSum[index - 1];
		}
	}


	/**
	 * 范围
	 *
	 * @param L l
	 * @param R 右
	 * @return int
	 * @author ZhangYi
	 */
	public int range(int L, int R) {
		if (R < L){
			throw new RuntimeException("R < L, 范围值不正确");
		}

		return L == 0 ? preSum[R] : preSum[R] - preSum[L - 1];
	}
}


class PrefixSum2 {
	private int[][] preSum;

	public PrefixSum2(int[] arr) {
		int N = arr.length;
		preSum = new int[N][N];
		for (int i = 0; i < N; i++){
			for (int j = i; j < N; j++){
				if (j == i){
					preSum[i][j] = arr[i];
				}else {
					preSum[i][j] = preSum[i][j - 1] + arr[j];
				}
			}
		}
	}


	public int range(int L, int R) {
		if (R < L){
			throw new RuntimeException("R < L, 范围值不正确");
		}
		return preSum[L][R];
	}
}